package org.noote.libs.voxel;

import org.noote.libs.sogle.Mesh;
import org.noote.libs.sogle.Object3D_Group;
import org.noote.libs.sogle.Vector3D;
import org.noote.libs.sogle.helper.Mesh_Box;

// http://paulbourke.net/geometry/polygonise/
// http://fr.wikipedia.org/wiki/Marching_tetrahedra

public class MeshBuilder {

	class Triangle
	{
		Vector3D [] p = new Vector3D[3];
	}
	class Cell
	{
		Vector3D [] p = new Vector3D[8];
		byte [] val = new byte[8];
	}
	
	public Object3D_Group buildAsCubes(Sprite3D sprite, byte isolevel)
	{
		Object3D_Group group = new Object3D_Group();
		float fMedX = -sprite.getSizeX()/2.0f, fMedY = -sprite.getSizeY()/2.0f, fMedZ = -sprite.getSizeZ()/2.0f;
		for(int x=0; x<sprite.getSizeX(); x++)
		{
			for(int y=0; y<sprite.getSizeY(); y++)
			{
				for(int z=0; z<sprite.getSizeZ(); z++)
				{
					if(sprite._datas[x][y][z]<isolevel)
					{
						Vector3D p = Vector3D.translateAndScale(new Vector3D(fMedX+x,		fMedY+y,	fMedZ+z  ), sprite.translation, sprite.scale);
						
						Mesh_Box m = new Mesh_Box(sprite.scale, sprite.scale, sprite.scale);
						m.setColor(sprite.red, sprite.green, sprite.blue, sprite.alpha);
						m.setPosition(p.x, p.y, p.z);
						group.add(m);
					}								
				}
			}
		}
		return group;
	}

	public Object3D_Group build(Sprite3D sprite, byte isolevel)
	{
		Object3D_Group group = new Object3D_Group();
		Cell cell = new Cell();
		float fMedX = -sprite.getSizeX()/2.0f, fMedY = -sprite.getSizeY()/2.0f, fMedZ = -sprite.getSizeZ()/2.0f;
		for(int x=0; x<sprite.getSizeX()-1; x++)
		{
			for(int y=0; y<sprite.getSizeY()-1; y++)
			{
				for(int z=0; z<sprite.getSizeZ()-1; z++)
				{
					cell.p[0] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+0, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[1] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+0, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[2] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+1, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[3] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+1, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[4] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+0, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[5] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+0, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[6] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+1, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[7] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+1, fMedZ+z+0), sprite.translation, sprite.scale);
				
					cell.val[0] = sprite._datas[x+0][y+0][z+0];
					cell.val[1] = sprite._datas[x+0][y+0][z+1];
					cell.val[2] = sprite._datas[x+0][y+1][z+1];
					cell.val[3] = sprite._datas[x+0][y+1][z+0];
					cell.val[4] = sprite._datas[x+1][y+0][z+0];
					cell.val[5] = sprite._datas[x+1][y+0][z+1];
					cell.val[6] = sprite._datas[x+1][y+1][z+1];
					cell.val[7] = sprite._datas[x+1][y+1][z+0];

					Triangle[] tris = _polygoniseCell(cell, isolevel);
					if(tris != null)
					{
						// TODO something better !
						short [] indices = new short[tris.length * 3];
						float [] vertices = new float[tris.length * 9];
						
						int i=0, v=0;
						for(Triangle tri : tris)
						{
							indices[i+0] = (short) i;
							indices[i+1] = (short)(i+1);
							indices[i+2] = (short)(i+2);
							i+=3;
							
							vertices[v+0] = tri.p[0].x;
							vertices[v+1] = tri.p[0].y;
							vertices[v+2] = tri.p[0].z;
							vertices[v+3] = tri.p[1].x;
							vertices[v+4] = tri.p[1].y;
							vertices[v+5] = tri.p[1].z;
							vertices[v+6] = tri.p[2].x;
							vertices[v+7] = tri.p[2].y;
							vertices[v+8] = tri.p[2].z;
							v+=9;						
						}
						
						Mesh m = new Mesh();
						m.setIndices(indices);
						m.setVertices(vertices);
						m.setColor(sprite.red, sprite.green, sprite.blue, sprite.alpha);
						group.add(m);
					}
				}
			}
		}
		return group;
	}

	protected Triangle[] _polygoniseCell(Cell grid, byte isolevel)
	{
		int i,ntriang = 0;
		int cubeindex = 0;
		Vector3D [] vertlist = new Vector3D[12];
		Triangle [] triangles = new Triangle[5];
		
		/*
	      Determine the index into the edge table which
	      tells us which vertices are inside of the surface
	   */
	   cubeindex = 0;
	   if (grid.val[0] < isolevel) cubeindex |= 1;
	   if (grid.val[1] < isolevel) cubeindex |= 2;
	   if (grid.val[2] < isolevel) cubeindex |= 4;
	   if (grid.val[3] < isolevel) cubeindex |= 8;
	   if (grid.val[4] < isolevel) cubeindex |= 16;
	   if (grid.val[5] < isolevel) cubeindex |= 32;
	   if (grid.val[6] < isolevel) cubeindex |= 64;
	   if (grid.val[7] < isolevel) cubeindex |= 128;

	   /* Cube is entirely in/out of the surface */
	   if (_edgeTable1[cubeindex] == 0)
	      return null;

	   /* Find the vertices where the surface intersects the cube */
	   if ((_edgeTable1[cubeindex] & 1)!=0)
	      vertlist[0] =
	         _vertexInterp(isolevel,grid.p[0],grid.p[1],grid.val[0],grid.val[1]);
	   if ((_edgeTable1[cubeindex] & 2)!=0)
	      vertlist[1] =
	         _vertexInterp(isolevel,grid.p[1],grid.p[2],grid.val[1],grid.val[2]);
	   if ((_edgeTable1[cubeindex] & 4)!=0)
	      vertlist[2] =
	         _vertexInterp(isolevel,grid.p[2],grid.p[3],grid.val[2],grid.val[3]);
	   if ((_edgeTable1[cubeindex] & 8)!=0)
	      vertlist[3] =
	         _vertexInterp(isolevel,grid.p[3],grid.p[0],grid.val[3],grid.val[0]);
	   if ((_edgeTable1[cubeindex] & 16)!=0)
	      vertlist[4] =
	         _vertexInterp(isolevel,grid.p[4],grid.p[5],grid.val[4],grid.val[5]);
	   if ((_edgeTable1[cubeindex] & 32)!=0)
	      vertlist[5] =
	         _vertexInterp(isolevel,grid.p[5],grid.p[6],grid.val[5],grid.val[6]);
	   if ((_edgeTable1[cubeindex] & 64)!=0)
	      vertlist[6] =
	         _vertexInterp(isolevel,grid.p[6],grid.p[7],grid.val[6],grid.val[7]);
	   if ((_edgeTable1[cubeindex] & 128)!=0)
	      vertlist[7] =
	         _vertexInterp(isolevel,grid.p[7],grid.p[4],grid.val[7],grid.val[4]);
	   if ((_edgeTable1[cubeindex] & 256)!=0)
	      vertlist[8] =
	         _vertexInterp(isolevel,grid.p[0],grid.p[4],grid.val[0],grid.val[4]);
	   if ((_edgeTable1[cubeindex] & 512)!=0)
	      vertlist[9] =
	         _vertexInterp(isolevel,grid.p[1],grid.p[5],grid.val[1],grid.val[5]);
	   if ((_edgeTable1[cubeindex] & 1024)!=0)
	      vertlist[10] =
	         _vertexInterp(isolevel,grid.p[2],grid.p[6],grid.val[2],grid.val[6]);
	   if ((_edgeTable1[cubeindex] & 2048)!=0)
	      vertlist[11] =
	         _vertexInterp(isolevel,grid.p[3],grid.p[7],grid.val[3],grid.val[7]);

	   /* Create the triangle */
	   ntriang = 0;
	   for (i=0; _triTable1[cubeindex][i]!=-1; i+=3) {
		  triangles[ntriang] = new Triangle(); 
	      triangles[ntriang].p[0] = vertlist[_triTable1[cubeindex][i+0]];
	      triangles[ntriang].p[1] = vertlist[_triTable1[cubeindex][i+1]];
	      triangles[ntriang].p[2] = vertlist[_triTable1[cubeindex][i+2]];
	      ntriang++;
	   }
	   
	   if(ntriang == 0)
		   return null;
	   
	   Triangle ret[] = new Triangle[ntriang];
	   for(i=0; i<ntriang; i++)
	   {
		   ret[i] = new Triangle();
		   ret[i].p[0] = triangles[i].p[0];
		   ret[i].p[1] = triangles[i].p[1];
		   ret[i].p[2] = triangles[i].p[2];
	   }

	   return ret;
	}
	
	// bug some where :(
	public Object3D_Group buildByTetrahedon(Sprite3D sprite, byte isolevel)
	{
		Object3D_Group group = new Object3D_Group();
		Cell cell = new Cell();
		float fMedX = -sprite.getSizeX()/2.0f, fMedY = -sprite.getSizeY()/2.0f, fMedZ = -sprite.getSizeZ()/2.0f;
		for(int x=0; x<sprite.getSizeX()-1; x++)
		{
			for(int y=0; y<sprite.getSizeY()-1; y++)
			{
				for(int z=0; z<sprite.getSizeZ()-1; z++)
				{
					cell.p[0] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+0, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[1] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+0, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[2] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+1, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[3] = Vector3D.translateAndScale(new Vector3D(fMedX+x+0, fMedY+y+1, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[4] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+0, fMedZ+z+0), sprite.translation, sprite.scale);
					cell.p[5] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+0, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[6] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+1, fMedZ+z+1), sprite.translation, sprite.scale);
					cell.p[7] = Vector3D.translateAndScale(new Vector3D(fMedX+x+1, fMedY+y+1, fMedZ+z+0), sprite.translation, sprite.scale);
				
					cell.val[0] = sprite._datas[x+0][y+0][z+0];
					cell.val[1] = sprite._datas[x+0][y+0][z+1];
					cell.val[2] = sprite._datas[x+0][y+1][z+1];
					cell.val[3] = sprite._datas[x+0][y+1][z+0];
					cell.val[4] = sprite._datas[x+1][y+0][z+0];
					cell.val[5] = sprite._datas[x+1][y+0][z+1];
					cell.val[6] = sprite._datas[x+1][y+1][z+1];
					cell.val[7] = sprite._datas[x+1][y+1][z+0];

					Triangle[] tris = _polygoniseCellByTetrahedon(cell, isolevel);
					if(tris != null)
					{
						// TODO something better !
						short [] indices = new short[tris.length * 3];
						float [] vertices = new float[tris.length * 9];
						
						int i=0, v=0;
						for(Triangle tri : tris)
						{
							indices[i+0] = (short) i;
							indices[i+1] = (short)(i+1);
							indices[i+2] = (short)(i+2);
							i+=3;
							
							vertices[v+0] = tri.p[0].x;
							vertices[v+1] = tri.p[0].y;
							vertices[v+2] = tri.p[0].z;
							vertices[v+3] = tri.p[1].x;
							vertices[v+4] = tri.p[1].y;
							vertices[v+5] = tri.p[1].z;
							vertices[v+6] = tri.p[2].x;
							vertices[v+7] = tri.p[2].y;
							vertices[v+8] = tri.p[2].z;
							v+=9;						
						}
						
						Mesh m = new Mesh();
						m.setIndices(indices);
						m.setVertices(vertices);
						m.setColor(sprite.red, sprite.green, sprite.blue, sprite.alpha);
						group.add(m);
					}
				}
			}
		}
		return group;
	}

	protected Triangle[] _polygoniseCellByTetrahedon(Cell grid, byte isolevel)
	{
		Triangle [][] t = new Triangle[6][2];
		
		t[0] = _polygoniseTriByTetrahedon(grid,isolevel,0,2,3,7);
		t[1] = _polygoniseTriByTetrahedon(grid,isolevel,0,2,6,7);
		t[2] = _polygoniseTriByTetrahedon(grid,isolevel,0,4,6,7);
		t[3] = _polygoniseTriByTetrahedon(grid,isolevel,0,6,1,2);
		t[4] = _polygoniseTriByTetrahedon(grid,isolevel,0,6,1,4);
		t[5] = _polygoniseTriByTetrahedon(grid,isolevel,5,6,1,4);

		int nTriangle = 0;
		for(int i=0; i<6; i++)
		{
			if(t[i] != null) nTriangle += t[i].length;
		}
		
		Triangle [] triangles = new Triangle[nTriangle];
		nTriangle = 0;
		for(int i=0; i<6; i++)
		{
			if(t[i] == null) continue;
			
			for(Triangle t2 : t[i])
			{
				triangles[nTriangle] = new Triangle();
				triangles[nTriangle].p[0] = t2.p[0];
				triangles[nTriangle].p[1] = t2.p[1];
				triangles[nTriangle].p[2] = t2.p[2];
				nTriangle++;
			}
		}
		
		return triangles;
	}
	
	/*
	   Polygonise a tetrahedron given its vertices within a cube
	   This is an alternative algorithm to polygonisegrid.
	   It results in a smoother surface but more triangular facets.

	                      + 0
	                     /|\
	                    / | \
	                   /  |  \
	                  /   |   \
	                 /    |    \
	                /     |     \
	               +-------------+ 1
	              3 \     |     /
	                 \    |    /
	                  \   |   /
	                   \  |  /
	                    \ | /
	                     \|/
	                      + 2

	   It's main purpose is still to polygonise a gridded dataset and
	   would normally be called 6 times, one for each tetrahedron making
	   up the grid cell.
	   Given the grid labelling as in PolygniseGrid one would call
	      PolygoniseTri(grid,iso,0,2,3,7);
	      PolygoniseTri(grid,iso,0,2,6,7);
	      PolygoniseTri(grid,iso,0,4,6,7);
	      PolygoniseTri(grid,iso,0,6,1,2);
	      PolygoniseTri(grid,iso,0,6,1,4);
	      PolygoniseTri(grid,iso,5,6,1,4);
	*/
	Triangle [] _polygoniseTriByTetrahedon(Cell grid, byte iso, int v0,int v1,int v2,int v3)
	{
	   int ntri = 0;
	   int triindex;
	   Triangle [] triangles = new Triangle[2];

	   /*
	      Determine which of the 16 cases we have given which vertices
	      are above or below the isosurface
	   */
	   triindex = 0;
	   if (grid.val[v0] < iso) triindex |= 1;
	   if (grid.val[v1] < iso) triindex |= 2;
	   if (grid.val[v2] < iso) triindex |= 4;
	   if (grid.val[v3] < iso) triindex |= 8;

	   /* Form the vertices of the triangles for each case */
	   switch (triindex) {
	   case 0x00:
	   case 0x0F:
	      break;
	   case 0x0E:
	   case 0x01:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v0],grid.p[v1],grid.val[v0],grid.val[v1]);
		  triangles[0].p[1] = _vertexInterp(iso,grid.p[v0],grid.p[v2],grid.val[v0],grid.val[v2]);
		  triangles[0].p[2] = _vertexInterp(iso,grid.p[v0],grid.p[v3],grid.val[v0],grid.val[v3]);
	      ntri++;
	      break;
	   case 0x0D:
	   case 0x02:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v1],grid.p[v0],grid.val[v1],grid.val[v0]);
	      triangles[0].p[1] = _vertexInterp(iso,grid.p[v1],grid.p[v3],grid.val[v1],grid.val[v3]);
	      triangles[0].p[2] = _vertexInterp(iso,grid.p[v1],grid.p[v2],grid.val[v1],grid.val[v2]);
	      ntri++;
	      break;
	   case 0x0C:
	   case 0x03:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v0],grid.p[v3],grid.val[v0],grid.val[v3]);
	      triangles[0].p[1] = _vertexInterp(iso,grid.p[v0],grid.p[v2],grid.val[v0],grid.val[v2]);
	      triangles[0].p[2] = _vertexInterp(iso,grid.p[v1],grid.p[v3],grid.val[v1],grid.val[v3]);
	      ntri++;
	      triangles[1] = new Triangle();
	      triangles[1].p[0] = triangles[0].p[2];
	      triangles[1].p[1] = _vertexInterp(iso,grid.p[v1],grid.p[v2],grid.val[v1],grid.val[v2]);
	      triangles[1].p[2] = triangles[0].p[1];
	      ntri++;
	      break;
	   case 0x0B:
	   case 0x04:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v2],grid.p[v0],grid.val[v2],grid.val[v0]);
	      triangles[0].p[1] = _vertexInterp(iso,grid.p[v2],grid.p[v1],grid.val[v2],grid.val[v1]);
	      triangles[0].p[2] = _vertexInterp(iso,grid.p[v2],grid.p[v3],grid.val[v2],grid.val[v3]);
	      ntri++;
	      break;
	   case 0x0A:
	   case 0x05:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v0],grid.p[v1],grid.val[v0],grid.val[v1]);
	      triangles[0].p[1] = _vertexInterp(iso,grid.p[v2],grid.p[v3],grid.val[v2],grid.val[v3]);
	      triangles[0].p[2] = _vertexInterp(iso,grid.p[v0],grid.p[v3],grid.val[v0],grid.val[v3]);
	      ntri++;
	      triangles[1] = new Triangle();
	      triangles[1].p[0] = triangles[0].p[0];
	      triangles[1].p[1] = _vertexInterp(iso,grid.p[v1],grid.p[v2],grid.val[v1],grid.val[v2]);
	      triangles[1].p[2] = triangles[0].p[1];
	      ntri++;
	      break;
	   case 0x09:
	   case 0x06:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v0],grid.p[v1],grid.val[v0],grid.val[v1]);
	      triangles[0].p[1] = _vertexInterp(iso,grid.p[v1],grid.p[v3],grid.val[v1],grid.val[v3]);
	      triangles[0].p[2] = _vertexInterp(iso,grid.p[v2],grid.p[v3],grid.val[v2],grid.val[v3]);
	      ntri++;
	      triangles[1] = new Triangle();
	      triangles[1].p[0] = triangles[0].p[0];
	      triangles[1].p[1] = _vertexInterp(iso,grid.p[v0],grid.p[v2],grid.val[v0],grid.val[v2]);
	      triangles[1].p[2] = triangles[0].p[2];
	      ntri++;
	      break;
	   case 0x07:
	   case 0x08:
		  triangles[0] = new Triangle();
		  triangles[0].p[0] = _vertexInterp(iso,grid.p[v3],grid.p[v0],grid.val[v3],grid.val[v0]);
		  triangles[0].p[1] = _vertexInterp(iso,grid.p[v3],grid.p[v2],grid.val[v3],grid.val[v2]);
		  triangles[0].p[2] = _vertexInterp(iso,grid.p[v3],grid.p[v1],grid.val[v3],grid.val[v1]);
	      ntri++;
	      break;
	   }

	   if(ntri == 0)
		   return null;
	   
	   Triangle ret[] = new Triangle[ntri];
	   for(int i=0; i<ntri; i++)
	   {
		   ret[i] = new Triangle();
		   ret[i].p[0] = triangles[i].p[0];
		   ret[i].p[1] = triangles[i].p[1];
		   ret[i].p[2] = triangles[i].p[2];
	   }

	   return ret;
	}

	/*
	   Linearly interpolate the position where an isosurface cuts
	   an edge between two vertices, each with their own scalar value
	*/
	protected Vector3D _vertexInterp(float isolevel, Vector3D p1, Vector3D p2, float valp1, float valp2)
	{
	   float mu = 0.0f;
	   Vector3D p = new Vector3D();

	   if (Math.abs(isolevel-valp1) < 0.00001f)
	      return(p1);
	   if (Math.abs(isolevel-valp2) < 0.00001f)
	      return(p2);
	   if (Math.abs(valp1-valp2) < 0.00001f)
	      return(p1);
	   
	   mu = (isolevel - valp1) / (valp2 - valp1);
	   p.x = (p1.x + mu * (p2.x - p1.x));
	   p.y = (p1.y + mu * (p2.y - p1.y));
	   p.z = (p1.z + mu * (p2.z - p1.z));

	   return(p);
	}	
	
	static int [] _edgeTable1 = {
		0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,
		0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,
		0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,
		0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,
		0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,
		0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,
		0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,
		0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,
		0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,
		0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,
		0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,
		0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,
		0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,
		0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,
		0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,
		0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,
		0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,
		0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,
		0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,
		0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,
		0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,
		0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,
		0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,
		0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,
		0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,
		0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,
		0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,
		0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,
		0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,
		0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,
		0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,
		0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0   };
	static int [][] _triTable1 =
	{
		{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},
		{3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1},
		{3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1},
		{3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1},
		{9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1},
		{9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
		{2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1},
		{8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1},
		{9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
		{4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1},
		{3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1},
		{1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1},
		{4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1},
		{4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1},
		{9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
		{5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1},
		{2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1},
		{9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1},
		{0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1},
		{2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1},
		{10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1},
		{4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1},
		{5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1},
		{5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1},
		{9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1},
		{0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1},
		{1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1},
		{10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1},
		{8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},
		{2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1},
		{7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1},
		{9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},
		{2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1},
		{11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1},
		{9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1},
		{5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1},
		{11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1},
		{11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
		{1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1},
		{9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1},
		{5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},
		{2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
		{0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1},
		{5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1},
		{6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1},
		{3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},
		{6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1},
		{5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1},
		{1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1},
		{10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},
		{6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},
		{8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},
		{7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},
		{3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1},
		{5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1},
		{0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1},
		{9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1},
		{8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1},
		{5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1},
		{0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},
		{6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1},
		{10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1},
		{10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},
		{8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1},
		{1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1},
		{3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},
		{0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1},
		{10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1},
		{3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1},
		{6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},
		{9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},
		{8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},
		{3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1},
		{6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1},
		{0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1},
		{10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1},
		{10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},
		{2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},
		{7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1},
		{7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1},
		{2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},
		{1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1},
		{11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1},
		{8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},
		{0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1},
		{7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
		{10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
		{2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1},
		{6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1},
		{7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1},
		{2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1},
		{1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1},
		{10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1},
		{10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1},
		{0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},
		{7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1},
		{6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1},
		{8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1},
		{9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1},
		{6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1},
		{4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1},
		{10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1},
		{8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1},
		{0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},
		{1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1},
		{8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1},
		{10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1},
		{4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1},
		{10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1},
		{5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
		{11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1},
		{9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1},
		{6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1},
		{7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1},
		{3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},
		{7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1},
		{9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},
		{3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},
		{6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},
		{9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1},
		{1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},
		{4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1},
		{7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1},
		{6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1},
		{3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1},
		{0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1},
		{6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1},
		{0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1},
		{11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1},
		{6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1},
		{5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},
		{9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1},
		{1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},
		{1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},
		{10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1},
		{0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1},
		{5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1},
		{10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1},
		{11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},
		{9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},
		{7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},
		{2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1},
		{8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},
		{9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1},
		{9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},
		{1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1},
		{9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1},
		{9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1},
		{5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1},
		{0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1},
		{10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1},
		{2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},
		{0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1},
		{0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},
		{9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},
		{5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1},
		{3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},
		{5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},
		{8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1},
		{0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},
		{9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1},
		{0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1},
		{1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1},
		{3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1},
		{4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1},
		{9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1},
		{11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},
		{11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1},
		{2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1},
		{9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1},
		{3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1},
		{1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1},
		{4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1},
		{4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1},
		{0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1},
		{3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1},
		{3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1},
		{0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1},
		{9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1},
		{1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
		{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
	};
}
